package base_Suanfa.erchashu;

import java.util.ArrayList;
import java.util.Arrays;

public class Prim {
    public static void main(String[] args) {
   char vertex[]={ 'A','B','C','D','E','F','G'};
   int size=vertex.length;
   int edges[][]={{0,7,0,5,0,0,0},{7,0,8,9,7,0,0},{0,8,0,0,5,0,0},{5,9,0,0,15,6,0},{0,7,5,15,0,8,9},{0,0,0,6,8,0,11},{0,0,0,0,9,11,0}};
        Graph graph=new Graph(size);
        MinTree minTree=new MinTree();
        minTree.createGraph(graph,size,vertex,edges);
        minTree.showGraph(graph);
        minTree.prim(graph,3);
    }

}
class Graph{
    int vertexSize;  //存放顶点的个数
    char [] vertex;   //存放顶点的数据
    int [][]edges; //存放一个权值的矩阵
    public Graph(int size){
        this.vertexSize=size;
        this.vertex=new char[size];
        this.edges=new int[size][size];
    }
}
class MinTree{
    //生成一个邻接矩阵
    public void createGraph(Graph graph,int size,char vertex[],int edges[][]){
      for(int i=0;i<size;i++){
          graph.vertex[i]=vertex[i];
          for(int j=0;j<size;j++){
   graph.edges[i][j]=edges[i][j];
          }
      }
    }
    public void showGraph(Graph graph){
    for(int edge[]:graph.edges){
        System.out.println(Arrays.toString(edge));
    }
    }
    public void prim(Graph graph,int v){
        //用来标记当前是否被访问
        int visited[]=new int[graph.vertexSize];
        visited[v]=1;   //当前结点记录为被访问
        int minV=-1;    //未被访问中最小路径的质点
        int minI=-1;
        //寻找最小权值的路径，默认为无穷大
        int minDistence=Integer.MAX_VALUE;
        //循环遍历k个结点,
        for(int k=1;k<graph.vertexSize;k++){
            //求出要确定每一次生成子图中最短路径并记录
            for(int i=0;i<graph.vertexSize;i++){
                for (int j=0;j<graph.vertexSize;j++){
                    if(visited[i]==1&&visited[j]==0&&graph.edges[i][j]!=0&&graph.edges[i][j]<minDistence){
                        minDistence=graph.edges[i][j];
                        //记录最小路径的下标   minV当前点 minI下一个点
                        minV=i;
                        minI=j;
                    }
                }
            }
            System.out.println(graph.vertex[minV]+","+graph.vertex[minI]+" "+minDistence);
            visited[minI]=1;
            minDistence=Integer.MAX_VALUE;
        }

    }
}

